package sliding_window

//713.给定一个正整数数组nums和整数 k 。
//请找出该数组内乘积小于k的连续的子数组的个数。

//示例 1:
//输入: nums = [10,5,2,6], k = 100
//输出: 8
//解释: 8个乘积小于100的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
//需要注意的是 [10,5,2] 并不是乘积小于100的子数组。

//示例 2:
//输入: nums = [1,2,3], k = 0
//输出: 0

//滑动窗口
//时间复杂度：O(n)，其中 n是nums 数组的长度。循环的时间复杂度为 O(n)，而 left 最多移动 n 次，因此总的时间复杂度为 O(n)。
//空间复杂度：O(1)
func numSubarrayProductLessThanK(nums []int, k int) int {
	left, right, product, cnt := 0, 0, 1, 0

	//入参判断
	if len(nums) == 0 {
		return 0
	}
	if k <= 1 {
		return 0
	}

	//expands widows
	for right < len(nums) {
		//先计算乘积
		product *= nums[right]

		//shrink windows 直到满足乘积小于k的条件
		for product >= k {
			//移除数据
			product /= nums[left]
			left++
		}

		//该窗口内就包含了了 right−left+1 个乘积小于 k 的连续子数组
		cnt += right - left + 1
		right++
	}

	return cnt
}
